8.6 KB · ⇊ 3 parts · ⤓ Micron 8.6 KB · ⤓ HTML 77.8 KB

top

Das Subdifferential ist eine Verallgemeinerung des Gradienten auf nicht differenzierbare konvexe Funktionen. Das Subdifferential spielt eine wichtige Rolle in der konvexen Analysis sowie der konvexen Optimierung.

• Definition

• Anschauung

• Beispiel

• Beschränktheit

• Beweis

• Differenzierbarkeit

• Literatur

Sei f : : R n → → R {\displaystyle f\colon \mathbb {R} ^{n}\to \mathbb {R} } eine konvexe Funktion. Ein Vektor g ∈ ∈ R n {\displaystyle g\in \mathbb {R} ^{n}} heißt Subgradient von f {\displaystyle f} an der Stelle x 0 {\displaystyle x_{0}} , wenn für alle x ∈ ∈ R n {\displaystyle x\in \mathbb {R} ^{n}} giltcite-ref-1[1]

f ( x ) ≥ ≥ f ( x 0 ) + ⟨ ⟨ g , x − − x 0 ⟩ ⟩ {\displaystyle f(x)\geq f(x_{0})+\langle g,x-x_{0}\rangle } ,

wobei ⟨ ⟨ ⋅ ⋅ , ⋅ ⋅ ⟩ ⟩ {\displaystyle \langle \cdot ,\cdot \rangle } das Standardskalarprodukt bezeichnet.

Das Subdifferential ∂ ∂ f ( x 0 ) {\displaystyle \partial f(x_{0})} ist die Menge aller Subgradienten von f {\displaystyle f} im Punkt x 0 {\displaystyle x_{0}} .cite-ref-2[2]

Existieren die folgenden Grenzwerte a = lim x → → x 0 − − f ( x ) − − f ( x 0 ) x − − x 0 , {\displaystyle a=\lim _{x\to x_{0}^{-}}{\frac {f(x)-f(x_{0})}{x-x_{0}}},} b = lim x → → x 0 + f ( x ) − − f ( x 0 ) x − − x 0 , {\displaystyle b=\lim _{x\to x_{0}^{+}}{\frac {f(x)-f(x_{0})}{x-x_{0}}},} so wird das Intervall [ a , b ] {\displaystyle [a,b]} aller Subgradienten das Subdifferential der Funktion f {\displaystyle f} bei x 0 {\displaystyle x_{0}} genannt und wird als ∂ ∂ f ( x 0 ) := [ a , b ] {\displaystyle \partial f(x_{0}):=[a,b]} geschrieben.

Für eine konvexe Funktion gilt a ≤ ≤ b {\displaystyle a\leq b} , für eine nicht konvexe Funktion braucht dies nicht zu gelten und dann ist ∂ ∂ f ( x 0 ) = ∅ ∅ {\displaystyle \partial f(x_{0})=\emptyset } .

Intuitiv bedeutet diese Definition für n = 1 {\displaystyle n=1} , dass der Graph der Funktion f {\displaystyle f} überall über der Geraden G {\displaystyle G} liegt, die durch den Punkt ( x 0 , f ( x 0 ) ) {\displaystyle (x_{0},f(x_{0}))} geht und die Steigung g {\displaystyle g} besitzt:

G = { ( x , y ) ∈ ∈ R 2 ∣ ∣ y = g ⋅ ⋅ ( x − − x 0 ) + f ( x 0 ) } {\displaystyle G=\{(x,y)\in \mathbb {R} ^{2}\mid y=g\cdot (x-x_{0})+f(x_{0})\}}

Da die Normalengleichung von G {\displaystyle G} gerade

− − g ⋅ ⋅ ( x − − x 0 ) + 1 ⋅ ⋅ ( y − − f ( x 0 ) ) = 0 {\displaystyle -g\cdot (x-x_{0})+1\cdot (y-f(x_{0}))=0}

ist, ist die Normale an G {\displaystyle G} also ( − − g , 1 ) ∈ ∈ R 2 {\displaystyle (-g,1)\in \mathbb {R} ^{2}} .

Im allgemeinen Fall n ≥ ≥ 1 {\displaystyle n\geq 1} liegt f {\displaystyle f} über der Hyperebene, die durch den Fußpunkt ( x 0 , f ( x 0 ) ) {\displaystyle (x_{0},f(x_{0}))} und die Normale ( − − g , 1 ) ∈ ∈ R n + 1 {\displaystyle (-g,1)\in \mathbb {R} ^{n+1}} gegeben ist.

Wegen des Trennungssatzes ist das Subdifferential einer stetigen konvexen Funktion überall nichtleer.

Das Subdifferential der Funktion f : : R → → R {\displaystyle f\colon \mathbb {R} \rightarrow \mathbb {R} } , x ↦ ↦ | x | {\displaystyle x\mapsto |x|} ist gegeben durch:

∂ ∂ f ( x 0 ) = { { − − 1 } x 0 < 0 [ − − 1 , 1 ] x 0 = 0 { 1 } x 0 > 0 {\displaystyle \partial f(x_{0})={\begin{cases}\{-1\}&x_{0}<0\\\left[-1,1\right]&x_{0}=0\\\{1\}&x_{0}>0\end{cases}}}

Eine ähnliche Eigenschaft ist bei der Lasso-Regression für die Herleitung der Soft-Threshold-Funktion wichtig.

Sei f : : R n → → R {\displaystyle f\colon \mathbb {R} ^{n}\rightarrow \mathbb {R} } stetig und sei X ⊂ ⊂ R n {\displaystyle X\subset \mathbb {R} ^{n}} beschränkt. Dann ist die Menge ⋃ ⋃ x 0 ∈ ∈ X ∂ ∂ f ( x 0 ) {\displaystyle \bigcup _{x_{0}\in X}\partial f(x_{0})} beschränkt.

Sei f : : R n → → R {\displaystyle f\colon \mathbb {R} ^{n}\rightarrow \mathbb {R} } stetig und sei X ⊂ ⊂ R n {\displaystyle X\subset \mathbb {R} ^{n}} beschränkt. Setze ε ε := sup | f ( U 1 ( X ) ¯ ¯ ) | {\displaystyle \varepsilon :=\sup |f({\overline {U_{1}(X)}})|} wobei U 1 ( X ) ¯ ¯ = { x ∈ ∈ R n ∣ ∣ d i s t ( x , X ) ≤ ≤ 1 } {\displaystyle {\overline {U_{1}(X)}}=\{x\in \mathbb {R} ^{n}\mid {\rm {dist}}(x,X)\leq 1\}} . Angenommen, ⋃ ⋃ x 0 ∈ ∈ X ∂ ∂ f ( x 0 ) {\displaystyle \bigcup _{x_{0}\in X}\partial f(x_{0})} ist nicht beschränkt, dann gibt es für R := 2 ε ε {\displaystyle R:=2\varepsilon } ein x 0 ∈ ∈ X {\displaystyle x_{0}\in X} und ein g ∈ ∈ ∂ ∂ f ( x 0 ) {\displaystyle g\in \partial f(x_{0})} mit ‖ ‖ g ‖ ‖ 2 > R = 2 ε ε {\displaystyle \|g\|_{2}>R=2\varepsilon } . Sei x := 1 ‖ ‖ g ‖ ‖ 2 g + x 0 {\displaystyle x:={\frac {1}{\|g\|_{2}}}g+x_{0}} . Somit sind x 0 , x ∈ ∈ U 1 ( X ) ¯ ¯ {\displaystyle x_{0},x\in {\overline {U_{1}(X)}}} . Wir erhalten die Abschätzung

g T ( x − − x 0 ) = 1 ‖ ‖ g ‖ ‖ 2 g T g = ‖ ‖ g ‖ ‖ 2 > 2 ε ε ≥ ≥ | f ( x ) − − f ( x 0 ) | ≥ ≥ f ( x ) − − f ( x 0 ) {\displaystyle g^{T}(x-x_{0})={\frac {1}{\|g\|_{2}}}g^{T}g=\|g\|_{2}>2\varepsilon \geq \left|f(x)-f(x_{0})\right|\geq f(x)-f(x_{0})} .

g {\displaystyle g} ist also kein Subgradient. Das ist ein Widerspruch.

Ist die Funktion differenzierbar in x 0 ∈ ∈ i n t d o m f {\displaystyle x_{0}\in \mathrm {int} \,\mathrm {dom} \,f} , so gilt:

∂ ∂ f ( x 0 ) = { ∇ ∇ f ( x 0 ) } {\displaystyle \partial f(x_{0})=\left\{\nabla f(x_{0})\right\}}

Siehe cite-ref-3[3] für einen Beweis.

Zudem gilt: Ist das Subdifferential ∂ ∂ f ( x 0 ) {\displaystyle \partial f(x_{0})} einelementig, so ist f {\displaystyle f} an der Stelle x 0 {\displaystyle x_{0}} differenzierbar.cite-ref-4[4]

cite-note-11. ↑ R. T. Rockafellar Convex analysis 1970., p.214

cite-note-22. ↑ R. T. Rockafellar Convex analysis 1970., p.215

cite-note-33. ↑ Yaron Singer: Advanced Optimzation. Abgerufen am 27. Januar 2022: „Proposition 4“

cite-note-44. ↑ R. T. Rockafellar: Convex Analysis. Band 28, 1970: „Theorem 25.1“